package problem187_Repeated_DNA_Sequences;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution {
	private static final Map<Character,Integer> map=new HashMap<>();
	static{
		map.put('A', 0);
		map.put('C', 1);
		map.put('G', 2);
		map.put('T', 3);
	}
	
	public List<String> findRepeatedDnaSequences(String s) {
		List<String> result=new LinkedList<>();
		char[] arr=s.toCharArray();
		Set<Integer> all=new HashSet<>();
		Set<Integer> added=new HashSet<>();
		int hash=0;
		for(int i=0;i<arr.length;i++){
			if(i<9){
				hash=(hash<<2)+map.get(arr[i]);
			}else{
				hash=(hash<<2)+map.get(arr[i]);
				//截取低20位
				hash=hash&((1<<20)-1);
				if(all.contains(hash)&&!added.contains(hash)){
					result.add(s.substring(i-9,i+1));
					added.add(hash);
				}else{
					all.add(hash);
				}
			}
		}
		return result;
	 }
}
